"""
Douglas–Peucker算法
曲线压缩算法
效果好，耗时
"""

import math


def douglas_peucker_reduce(points, epsilon):
    # 获取点列表长度
    length = len(points)
    # 创建一个存储点是否保留的列表，初始都为True
    markers = [True] * length

    # 递归简化曲线
    def recursive_simplify(points, start, end, epsilon, level):
        # 如果只有一个点，则无需简化
        if start + 1 == end:
            return

        # 寻找最大距离点
        max_dist = 0
        index = 0
        for i in range(start + 1, end):
            # 计算点到直线的距离
            dist = get_perpendicular_distance(points[start], points[end], points[i])
            if dist > max_dist:
                max_dist = dist
                index = i

        # 如果距离大于epsilon，则递归简化间隔的点
        if max_dist > epsilon:
            recursive_simplify(points, start, index, epsilon, level + 1)
            recursive_simplify(points, index, end, epsilon, level + 1)
        else:
            # 否则标记所有在该线段上的点不保留
            for i in range(start + 1, end):
                markers[i] = False

    # 初始调用递归函数
    recursive_simplify(points, 0, length - 2, epsilon, 0)

    # 构建简化后的点列表
    simplified_points = [points[0]]
    for i in range(1, length):
        if markers[i]:
            simplified_points.append(points[i])
    simplified_points.append(points[-1])

    return simplified_points


# 计算点到直线的垂直距离
def get_perpendicular_distance(p1, p2, p0):
    x1, y1 = p1
    x2, y2 = p2
    x0, y0 = p0
    den = math.sqrt((y2 - y1) ** 2 + (x2 - x1) ** 2)
    if den == 0:  # 防止p1和p2重合导致len == 0
        return 0
    num = abs((y2 - y1) * x0 - (x2 - x1) * y0 + x2 * y1 - y2 * x1)
    return num / den

